﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution34
{
    public int[] SearchRange2(int[] nums, int target)//这个思路报错
    {
      

        int[] res=new int[2];
        res[0] = -1;
        res[1] = -1;
        //先使用二分法找到8任意一个
        if (nums.Length == 0) return res;
        if (nums.Length == 1)
        {

            if(nums[0] != target)
            {
                return res;
            }

        }
        


        int left = 0;
        int right = nums.Length - 1;
        int mid = (left + right + 1) / 2;
        while (left <= right)
        {

            if (target < nums[mid])
            {

                left = mid - 1;
            }
            else if (target == nums[mid])
            {

                left = mid;
                right = mid;
                while (nums[left] == target)
                {
                    left--;
                }
                while (nums[right] == target)
                {
                    right++;
                }
                res[0] = left + 1;
                res[1] = right - 1;
                break;
            }
            else
            {
                right = mid + 1;
            }
            mid = (left + right + 1) / 2;
        }
        


       

        return res;

    }

    private bool FindTarget(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;
        int mid = (left + right + 1) / 2;
        while (left <= right)
        {

            if (target < nums[mid])
            {

                left = mid - 1;
            }else if(target == nums[mid])
            {

                left = mid;
                right = mid;
                while (nums[left] == target)
                {
                    left--;
                }
                while (nums[right] == target)
                {
                    right++;
                }

                break;
            }
            else
            {
                right = mid + 1;
            }
            mid = (left + right + 1) / 2;
        }
        return false;

    }
    //寻找比目标值大的，和第一个等于目标值的
    public int[] SearchRange(int[] nums, int target)
    {
        int[] res = new int[2];
      
        int lower= SearchLower(nums, target);
        int higher = SearchHigher(nums, target)+1;
        if(lower <= higher&& higher<nums.Length&& nums[lower] ==target && nums[higher] == target)
        {
            res[0] = lower;
            res[1] = higher;
        }
        else
        {
            res[0] = -1;
            res[1] = -1;
        }

        return res;

    }

 int SearchHigher(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;
        int mid = (left + right + 1) / 2;
        int res = 0;
        while (left <= right)
        {

            if (target < nums[mid])
            {
                right = mid - 1;
               
            }
            else
            {
                left = mid + 1;
                res = mid;//先记录一下，后面还会更新
            }
            mid = (left + right + 1) / 2;
        }
        return res;

    }int SearchLower(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;
        int mid = (left + right + 1) / 2;
        int res = 0;
        while (left <= right)
        {

            if (target <= nums[mid])
            {
                right = mid - 1;//找到target记录一下，但是也要更新right，继续查找左边的
                res = mid;//先记录一下，后面还会更新
            }
            else
            {
                left = mid + 1;
            
            }
            mid = (left + right + 1) / 2;
        }
        return res;

    }
}
class Program34
{
    static void Main34(string[] args)
    {

        //int[] nums = [5, 7, 7, 8, 8, 10];
        int[] nums = [];
        int target = 8;
        Solution34 solution = new Solution34();
        int[] res=solution.SearchRange(nums, 0);
        Console.WriteLine(res[0]);
        Console.WriteLine(res[1]);
    }
}
